package com.frank.test;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.Arrays;


/**
 * Created by Administrator on 2018/10/11 0011.
 */
public class SortTest2 {


    @Test
    public void run() {
//        int nums[] = new int[10];
//        for (int i = 0; i < 10; i++) {
//            nums[i] = (int) (Math.random() * 50);
//        }
        System.out.println(this.getClass().getClassLoader());
        int[] nums = new int[]{11,9,7,10,8};
        System.out.println("排序前：" + Arrays.toString(nums));
        quick_sort(nums, 0, nums.length - 1);
        System.out.println("排序后：" + Arrays.toString(nums));
    }

    /**
     * 选择排序
     * 跟冒泡相比优点是减少了换的次数
     * 时间复杂度 =  (n-1) + (n-2)+...+1 = n~2 - (n^2)/2 = n^2/2
     *
     * @param nums
     */
    public void sel_sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min])
                    min = j;
            }
            int temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
        }
    }

    /**
     * 插入排序
     *
     * @param nums
     */
    public void ins_sort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int k = i;
            while (k > 0 && nums[k - 1] > key) {
                nums[k] = nums[k - 1];
                k--;
            }
            nums[k] = key;
        }
    }

    /**
     * 快速排序
     */
    public void quick_sort(int[] nums, int low, int high) {
        if (low > high) {
            return;
        }
        int start = low;
        int end = high;
        int key = nums[low];
        int temp;

        while (end > start) {
            while (end > start && nums[end] >= key) {
                end--;
            }

            while (end > start && nums[start] <= key) {
                start++;
            }

            //如果满足条件则交换
            if (end > start) {
                temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
            }
        }
        //最后将基准为与start和end相等位置的数字交换
        nums[low] = nums[start];
        nums[start] = key;
        //递归调用左半数组
        quick_sort(nums, low, end - 1);
        //递归调用右半数组
        quick_sort(nums, end + 1, high);
    }
}
